/*
 * MincostMaxflow.h
 *
 *  Created on: Mar 8, 2017
 *      Author: along
 */

#ifndef MINCOSTMAXFLOW_H_
#define MINCOSTMAXFLOW_H_

#include "Graph.h"
#include "my_io.h"
#include <vector>
#include <queue>

using namespace std;

class MincostMaxflow {
private:
	vector<Edge> e;
	vector<int> head,pre,dis;
	vector<bool> vis;
	int tol,size_g;
public:
	MincostMaxflow(Graph g_t)
	{
		size_g = g_t.size();
		head.resize(size_g,-1);
		pre.resize(size_g,-1);
		dis.resize(size_g,INF);
		vis.resize(size_g,false);
		tol = 0;
		for(int i=0;i<size_g;++i)
		{
			head[i] = -1;
		}
		transform(g_t);
	}
	
	void transform(Graph g)
	{
		vector<Edge> e_g = g.get_all_edges();
		int len = e_g.size();
		e.resize(len*2);
		for(int i = 0;i < len;++i)
		{
			Edge e_t = e_g[i];
			addEdge(e_t.from,e_t.to,e_t.cap,e_t.cost);
		}
	}
	
	void addEdge(int from,int to,int cap,int cost)
	{
		Edge e_p = Edge(from,to,cap,cost);
		e_p.next = head[from];
		e[tol] = e_p;
		head[from] = tol;
		++tol;
		
		Edge e_n = Edge(to,from,0,-cost);
		e_n.next = head[to];
		e[tol] = e_n;
		head[to] = tol;
		++tol;
	}
	bool spfa(int s,int t)
	{
		queue<int> q;
		for(int i=0;i<size_g;++i)
		{
			dis[i] = INF;
			vis[i] = false;
			pre[i] = -1;
		}
		dis[s] = 0;
		vis[s] = true;
		q.push(s);
		while(!q.empty())
		{
			int from = q.front();
			q.pop();
			vis[from] = false;
			for(int i = head[from];i != -1;i = e[i].next)
			{
				int to = e[i].to;
				if(e[i].cap > e[i].flow && dis[to] > dis[from] + e[i].cost)
				{
					dis[to] = dis[from] + e[i].cost;
					pre[to] = i;
					if(!vis[to])
					{
						vis[to] = true;
						q.push(to);
					}
				}
			}
		}
		if(pre[t] == -1)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	Graph restore()
	{
		Graph g_t(size_g);
		int len = e.size();
		for(int i=0;i<len;i+=2)
		{
			g_t.insert_edge(e[i]);
		}
		return g_t;
	}
	int calculate(int s,int t,Graph& g,int* flow)
	{
		int cost = 0;
		(*flow) = 0;
		while(spfa(s,t))
		{
			int min = INF;
			for(int i = pre[t];i != -1;i = pre[e[i^1].to])
			{
				if(min > e[i].cap - e[i].flow)
				{
					min = e[i].cap - e[i].flow;
				}
			}
			for(int i = pre[t];i != -1;i = pre[e[i^1].to])
			{
				e[i].flow += min;
				e[i^1].flow -= min;
				cost += e[i].cost*min;
			}
			(*flow) += min;
		}
		g = restore();
		// PRINTF("inside MCMF cost : %d flow : %d\n",cost,*flow);
		return cost;
	}
};

#endif /* MINCOSTMAXFLOW_H_ */
